home *** CD-ROM | disk | FTP | other *** search
/ Nautilus 1992 July / Nautilus-3-8 / Nautilus-3-8.bin / Tools & Utilities / Techy Stuff / Source ƒ / byacc-MPW Folder / warshall.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-14  |  3.1 KB  |  125 lines
  1. /*
  2.  * Copyright (c) 1989 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Robert Paul Corbett.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #ifndef lint
  38. static char sccsid[] = "@(#)warshall.c    5.3 (Berkeley) 6/1/90";
  39. #endif /* not lint */
  40.  
  41. #include "defs.h"
  42.  
  43. transitive_closure(R, n)
  44. unsigned *R;
  45. int n;
  46. {
  47.     register int rowsize;
  48.     register unsigned mask;
  49.     register unsigned *rowj;
  50.     register unsigned *rp;
  51.     register unsigned *rend;
  52.     register unsigned *ccol;
  53.     register unsigned *relend;
  54.     register unsigned *cword;
  55.     register unsigned *rowi;
  56.  
  57.     rowsize = WORDSIZE(n);
  58.     relend = R + n*rowsize;
  59.  
  60.     cword = R;
  61.     mask = 1;
  62.     rowi = R;
  63.     while (rowi < relend)
  64.     {
  65.     ccol = cword;
  66.     rowj = R;
  67.  
  68.     while (rowj < relend)
  69.     {
  70.         if (*ccol & mask)
  71.         {
  72.         rp = rowi;
  73.         rend = rowj + rowsize;
  74.         while (rowj < rend)
  75.             *rowj++ |= *rp++;
  76.         }
  77.         else
  78.         {
  79.         rowj += rowsize;
  80.         }
  81.  
  82.         ccol += rowsize;
  83.     }
  84.  
  85.     mask <<= 1;
  86.     if (mask == 0)
  87.     {
  88.         mask = 1;
  89.         cword++;
  90.     }
  91.  
  92.     rowi += rowsize;
  93.     }
  94. }
  95.  
  96. reflexive_transitive_closure(R, n)
  97. unsigned *R;
  98. int n;
  99. {
  100.     register int rowsize;
  101.     register unsigned mask;
  102.     register unsigned *rp;
  103.     register unsigned *relend;
  104.  
  105.     transitive_closure(R, n);
  106.  
  107.     rowsize = WORDSIZE(n);
  108.     relend = R + n*rowsize;
  109.  
  110.     mask = 1;
  111.     rp = R;
  112.     while (rp < relend)
  113.     {
  114.     *rp |= mask;
  115.     mask <<= 1;
  116.     if (mask == 0)
  117.     {
  118.         mask = 1;
  119.         rp++;
  120.     }
  121.  
  122.     rp += rowsize;
  123.     }
  124. }
  125.